// Package day_04_tree levelorder_range
// @Title day_04_tree
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/8/30 16:58
// @Create  2021/8/30 16:58
package day_04_tree

// LevelOrder 使用队列实现二叉树的层序遍历
func LevelOrder(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	queue := make([]*TreeNode, 0) // 申请一个队列
	queue = append(queue, root)
	for len(queue) > 0 {
		temp := queue[0]
		queue = queue[1:] // 从队列中删除一个数据
		ans = append(ans, temp.Val)
		if temp.Left != nil {
			queue = append(queue, temp.Left)
		}
		if temp.Right != nil {
			queue = append(queue, temp.Right)
		}
	}
	return ans
}

// LevelOrderII 层序遍历进阶版
func LevelOrderII(root *TreeNode) [][]int {
	ret := [][]int{}
	if root == nil {
		return ret
	}
	q := []*TreeNode{root} //
	for i := 0; len(q) > 0; i++ {
		ret = append(ret, []int{})
		p := []*TreeNode{}
		for j := 0; j < len(q); j++ {
			node := q[j]
			ret[i] = append(ret[i], node.Val)
			if node.Left != nil {
				p = append(p, node.Left)
			}
			if node.Right != nil {
				p = append(p, node.Right)
			}
		}
		q = p // 下扎一层
	}
	return ret
}
